/*
    created:2023/4/22   
    filename: BST.c
    author: 李东霖
    purpose：二叉排序树的数据结构和基本操作
*/
#include "BST.h"

//操作  
//在树tree中插入元素elem 返回值：1-成功 0-失败,tree存在元素elem -1-传入参数错误  
int Insert(BSTree *tree,ElemType *elem)
{
    if(elem == NULL) return -1;
    //如果他是空结点，那么elem就是他的根结点
    if((*tree) == NULL)
    {
        *tree = (BSTree)malloc(sizeof(BSTNode));
        (*tree)->rchild = (*tree)->lchild = NULL;
        memcpy(&(*tree)->data,elem,sizeof(ElemType));
        return 1;
    }
    //他不是空树，我们来插入  
    //存在元素elem
    if(*elem == (*tree)->data) return 0;
    //该结点比elem大，走左边
    if(*elem < (*tree)->data) Insert(&(*tree)->lchild,elem);
    else Insert(&(*tree)->rchild,elem);
}

//在树tree中插入元素elem 返回值：1-成功 0-失败,tree存在元素elem -1-传入参数错误  
int Insert1(BSTree *tree,ElemType *elem)
{
    //我们试一下非递归的方法  
    if(elem == NULL) return -1;
    //如果他是空结点，那么elem就是他的根结点
    if((*tree) == NULL)
    {
        *tree = (BSTree)malloc(sizeof(BSTNode));
        (*tree)->rchild = (*tree)->lchild = NULL;
        memcpy(&(*tree)->data,elem,sizeof(ElemType));
        return 1;
    }
    BSTNode* press = NULL;//保存双亲结点  
    BSTNode* ss = *tree;//用于查找的结点  
    int rl = 0;//记录ss是双亲结点的左子树还是右子树 0-左子树 1-右子树 
    while(ss != NULL)
    {
        if(*elem == ss->data) return 0;

        press = ss;
        if(*elem < ss->data) rl = 0,ss = ss->lchild; 
        else rl = 1,ss = ss->rchild; 
    }
    ss = (BSTNode*)malloc(sizeof(BSTNode));
    memcpy(&ss->data,elem,sizeof(ElemType));
    ss->rchild = ss->lchild = NULL;
    //处理press的指向
    if(rl == 0) press->lchild = ss;
    else press->rchild = ss;
}

//使用数组序列创建一个BST
void CreateBST(BSTree* tree,ElemType *elemarray,int len)
{
    if(elemarray == NULL) return;
    *tree = NULL;
    for(int i = 0;i != len; ++i)
    {
        Insert(tree,elemarray+i);
        // Insert1(tree,elemarray+i);
    }
}

//在树tree中查找元素elem 成功返回找到的结点，失败返回NULL
BSTNode* Find(BSTree tree,ElemType *elem)
{
    if(tree == NULL || elem == NULL)return NULL;
    if(tree->data == *elem) return tree;
    if(tree->data > *elem) return Find(tree->lchild,elem);   
    else return Find(tree->rchild,elem);   
}

//在树tree中查找元素elem 成功返回找到的结点，失败返回NULL
BSTNode* Find1(BSTree tree,ElemType *elem)
{
    //非递归的方法
    if(tree == NULL || elem == NULL)return NULL;
    BSTNode* p = tree;
    while(p != NULL)
    {
        if(p->data == *elem) return p;
        if(p->data > *elem) p = p->lchild;
        else p = p->rchild;
    }
    return NULL;
}

//在树tree中删除元素elem 返回值：1-成功 0-失败（tree没有元素elem）-1-传入的参数错误  
int Delete(BSTree *tree,ElemType *elem)
{
    //删除时结点出现的4种情况 
    if(tree == NULL || elem == NULL)return -1;
    
    //1.删除根结点
    if((*tree)->data == *elem && (*tree)->lchild == NULL  
       && (*tree)->rchild == NULL)
    {
        free(*tree);
        *tree = NULL;
        return 1;
    }
    //找到要删除的结点
    BSTNode* press = NULL;
    BSTNode* ss = *tree;
    int rl = 0;//记录ss是双亲结点的左子树还是右子树 0-左子树 1-右子树 
    while(ss != NULL && ss->data != *elem)
    {
        press = ss;
        if(ss->data > *elem) rl = 0,ss = ss->lchild;
        else rl = 1,ss = ss->rchild;
    }
    if(ss == NULL) return 0;
    //2.删除的叶子结点 
    if(ss->lchild ==NULL && ss->rchild == NULL)
    {
        free(ss);
        if(rl == 0) press->lchild = NULL;
        else press->rchild = NULL;
        return 1;
    }
    //3.如果删除的结点只有左子树或者右子树  让子树代替自己
    if(ss->lchild == NULL || ss->rchild == NULL)
    {
        if(ss->lchild != NULL)
        {
            if(rl == 0) press->lchild = ss->lchild;
            else press->rchild = ss->lchild;
        }
        else 
        {
            if(rl == 0) press->lchild = ss->rchild;
            else press->rchild = ss->rchild;
        }
        return 1;
    }
    //4.删除的元素有左子树和右子树  
    //将左子树的最右结点代替ss并删除这个最右结点  
    //或者是右子树的最左结点代替自己并删除这个最左结点
    BSTNode* pre = ss;
    BSTNode* p = ss->lchild;
    int rl1 = 0;
    while(p->rchild != NULL)
    {
        rl1 = 1;
        pre = p;
        p = p->rchild;
    }
    memcpy(&ss->data,&p->data,sizeof(ElemType));
    //修改双亲结点pre的右指针指向p，p的左子树可以为空  
    if(rl1 == 0)
    {
        pre->lchild = p->lchild;
    }
    else pre->rchild = p->lchild;
    free(p);
    return 1;
}

// 求二叉树的高度。
int TreeDepth(BSTree tree)
{
    if(tree == NULL)return 0;
    int ll = TreeDepth(tree->lchild);
    int rr = TreeDepth(tree->rchild);
    return ll > rr ? ll+1 : rr+1;
}

// 访问结点元素。
void visit(BSTNode *Node)
{
    if(Node == NULL) return;
    printf("%d",Node->data);
}

// 采用递归的方法对二叉树的先序遍历。
void PreOrder(BSTree tree)
{
    if(tree == NULL) return;
    printf("%d",tree->data);
    PreOrder(tree->lchild);
    PreOrder(tree->rchild);
}

// 采用递归的方法对二叉树的中序遍历。
void InOrder(BSTree tree)
{
    if(tree == NULL) return;
    
    InOrder(tree->lchild);
    printf("%d  ",tree->data);
    InOrder(tree->rchild);   

}

// 采用递归的方法对二叉树的后序遍历。
void PostOrder(BSTree tree)
{  
    if(tree == NULL) return;
    
    PostOrder(tree->lchild);
    PostOrder(tree->rchild);
    printf("%d",tree->data);
}
